package hot;

/**
 * @author lakersUp
 * @Classname      最长回文子串
 * @Description     中心扩散法
 *                  动态规划: 枚举子串长度跟左边界
 * @Date 2022/3/8 10:47
 * @Version 1.0
 */
public class Hot5longestPalindrome {
    int max=0;
    int[] index=new int[2];
    public String longestPalindrome(String s) {
        for(int i=0;i<s.length();i++){
            dfs(s,i,i);
            dfs(s,i,i+1);
        }
        return s.substring(index[0],index[1]+1);
    }

    private void dfs(String s, int i, int j) {
        if(i>=0 && j<=s.length()-1 && s.charAt(i)==s.charAt(j)){
            if(j-i+1>max){
                max=j-i+1;
                index[0]=i;
                index[1]=j;
            }
            dfs(s, i-1, j+1);
        }
    }
}
